//
//  HashTable.cpp
//  cpp
//
//  Created by xueshan1 on 2019/9/17.
//  Copyright © 2019 xueshan1. All rights reserved.
//

#include <stdio.h>
#include <string>
#include <vector>
#include <map>

using namespace std;
using std :: vector;

// key - value 映射
void test(){
    map<int,string> m1;
    m1[1] = "a";
    
    map<string,int> m2;
    m2["abc"] = 123;
    
}

#pragma mark - 子数组之和 为0 
//给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置
void sumOfsubArray_1(vector<int>array){
    vector<int>res; //存索引
    for (int i = 0; i<array.size(); i++) {
        int sum = 0;
        for (int j = i; j<array.size(); j++) {
            sum += array[i];
            if (sum == 0) {
                res.push_back(i);
                res.push_back(j);
            }
            
        }
        
    }
}
//https://blog.csdn.net/weixin_41413441/article/details/81045742
void sumOfsubArray_2(vector<int>array){
    vector<int>res;
    map<int,int>m;
    int sum = 0;
    for (int i = 0; i<array.size(); i++) {
        sum += array[i];
        if (m.find(sum) != m.end()) {//map存在, 有存在的, 说明这一段之和为0,(这一段相加抵消了,又回到了之前的和)
            res.push_back(m[sum] + 1);
            res.push_back(i);
        }
        
        m[sum] = i;//记录从0 到当前为止所有数的和
        
    }
    
}


#pragma mark - 两数组的交集
//给出两个数组，写出一个方法求出它们的交集
void intersectOfTwoArray(vector<int>a1,vector<int>a2){
    vector<int>intersetArr;
    map<int,int>m;
    for (int i = 0; i<a1.size(); i++) {
        m[a1[i]] += 1;
    }
    for (int j = 0; j<a2.size(); j++) {
        if (m[a2[j] >= 1]) {//a1中有了
            intersetArr.push_back(a2[j]);
        }
    }
    
}

#pragma mark -  两数之和
void sumOfTwoNumber(){
    vector<int>arr = {1,2,4,6,8,9};
    int target = 10;
    //
    vector<int>result;
    map<int,int>m;
    for (int i = 0; i<arr.size(); i++) {
        int cha = target - arr[i];
        m[cha] = i+1;
    }
    
    for (unsigned long j = arr.size() -1; j>0; j--) {
        if (m.find(arr[j]) != m.end()) { //找到了下标 j 存在

            result.push_back(m[arr[j]]);
            result.push_back(j);
        }
    }
    
    
}

#pragma mark -  给定一个字符串，请找出其中无重复字符的最长子字符串。
//滑动窗口
void longestSubString(string str){
    int len = str.length();
    map<char,int>m;
    int maxLenght = 0;
    int i = 0,j = 0;
    
    while (i<len && j<len) {
        char c = str[j];
        if (m.find(c) == m.end()) {//没有
            m[c]++;
            j++;
            maxLenght = max(maxLenght, j-i);
        }else{
            
            m.clear();
            i++;
            j = i;
            
        }
        
    }
    
    
    
}











